package my.test.datastructures.heap;

import java.util.ArrayList;

/**
 * @author LalitR
 */
public class HeapSortApp {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		heapSort();
	}
	
	private static void heapSort() {
		System.out.println("\n******* Heap Sort *******");
		
		int a[] = {2, 5, 9, 4, 8, 0, 1, 7, 6, 3};
		int size = a.length;
		
		HeapForSort theHeap = new HeapForSort(size);
		for (int j = 0; j < size; j++) {
			Node newNode = new Node(a[j]);
			theHeap.insertAt(j, newNode);
			theHeap.incrementSize();
		}
		
		theHeap.displayHeap(); // array in heap not correctly positioned nodes
		
		for(int k = size/2-1; k >= 0; k--) // make random array into heap
			theHeap.trickleDown(k);
		theHeap.displayHeap();
		
		for (int i =0, j = size - 1; j >= 0; j--,i++) // remove from heap and
		{ 	// store at array end
			Node biggestNode = theHeap.remove();
			theHeap.insertAt(j, biggestNode);
			
			a[i] = biggestNode.getKey();
		}
		
		System.out.print("Sorted Array: ");
		displayArray(a);
	}
	
	/**
	 * Display the array contents
	 * @param a
	 */
	private static void displayArray(int[] a) {
		ArrayList<Integer> al = new ArrayList<Integer>();
		for (int i = 0; i < a.length; i++) {
			al.add(a[i]);
		}
		System.out.println(al);
	}
}


class HeapForSort {
	private Node[] heapArray;
	private int maxSize; 		
	private int currentSize; // number of nodes in array
	
	public HeapForSort(int size) {
		maxSize = size;
		currentSize = 0;
		heapArray = new Node[maxSize];
	}
	
	public boolean isEmpty() {
		return (currentSize == 0);
	}
	
	public void incrementSize() {
		currentSize++;
	}
	
	public void insertAt(int index, Node node) {
		heapArray[index] = node;
	}
	
	public Node remove() {
		Node root = heapArray[0]; 				 // keep a copy of root
		heapArray[0] = heapArray[--currentSize]; // root <- last (last node becomes root)
		trickleDown(0); 
		return root; 
	}
	
	public void trickleDown(int index) {
		int largerChild;
		Node top = heapArray[index]; // keep a copy of node at index
		
		while(index < currentSize/2) { // while node has at least one child
			int leftChild = 2*index + 1;
			int rightChild = leftChild + 1;
			
			if (rightChild < currentSize && // (i.e. rightChild exists?)
				heapArray[leftChild].getKey() < heapArray[rightChild].getKey()) {
				largerChild = rightChild;
			} else {
				largerChild = leftChild;
			}
			
			// top >= largerChild?
			if(top.getKey() >= heapArray[largerChild].getKey())
				break;
			
			heapArray[index] = heapArray[largerChild];
			index = largerChild; // go down
		}
		heapArray[index] = top; // index <- root
	}
	
	public void displayHeap() {
		System.out.print("heapArray: "); // array format
		for (int m = 0; m < currentSize; m++)
			if (heapArray[m] != null)
				System.out.print(heapArray[m].getKey() + " ");
			else
				System.out.print("--");
		System.out.println();
	}
}
